Mô hình chuỗi markov là gì? Các bài báo nghiên cứu khoa học

Định nghĩa tổng quát về Mô hình Chuỗi Markov

Mô hình Chuỗi Markov là một hệ thống ngẫu nhiên rời rạc theo thời gian, trong đó xác suất chuyển đổi sang trạng thái tiếp theo chỉ phụ thuộc vào trạng thái hiện tại, hoàn toàn không phụ thuộc vào lịch sử quá khứ. Đặc tính này, gọi là “Markov property”, được biểu diễn qua công thức:

$P\bigl(X_{n+1}=j \mid X_n=i, X_{n-1},\dots\bigr)=P\bigl(X_{n+1}=j\mid X_n=i\bigr).$

Chuỗi Markov thường được mô tả qua dãy biến ngẫu nhiên $\{X_n\}$ và không gian trạng thái rời rạc $S=\{s_1,s_2,\dots\}$. Mỗi bước nhảy xác suất từ trạng thái $s_i$ sang $s_j$ được định nghĩa bởi phần tử ma trận $p_{ij}$. Khi số bước nhảy tăng lên, sự phụ thuộc vào trạng thái ban đầu dần giảm nếu chuỗi thỏa mãn điều kiện ergodic.

• Markov property: chỉ nhớ trạng thái hiện tại.
• Không gian trạng thái: tập rời rạc các giá trị khả dĩ.
• Ma trận chuyển tiếp: tổng các hàng bằng 1, $p_{ij}\ge0$.

Lịch sử và phát triển

Khái niệm Chuỗi Markov ra đời vào năm 1906, khi nhà toán học Nga Andrey Markov công bố bài báo đầu tiên sử dụng chuỗi xác suất để phân tích chuỗi các chữ cái trong văn bản Pushkin. Công trình này đã mở ra hướng đi mới trong lý thuyết xác suất xét đến tính phụ thuộc giữa các sự kiện tuần tự.

Sang giữa thế kỷ 20, các nhà khoa học phương Tây mở rộng ứng dụng chuỗi Markov vào lý thuyết hàng chờ, xử lý tín hiệu và mô hình hóa dữ liệu kinh tế. Năm 1953, Kolmogorov và Feller đóng góp các định lý cơ bản về phân phối ổn định và tính mạnh chuỗi vô hạn.

Hiện nay, Chuỗi Markov là nền tảng của các mô hình xác suất phức tạp hơn như Chuỗi Markov ẩn (HMM), được ứng dụng trong nhận dạng giọng nói, xử lý ngôn ngữ tự nhiên, và mô phỏng gene học. Hàng loạt thư viện phần mềm như MATLAB, R, Python Statsmodels đều tích hợp hàm hỗ trợ phân tích Markov.

Các thành phần cơ bản

Tập trạng thái (State Space) $S=\{s_1,s_2,\dots,s_N\}$ xác định danh sách các trạng thái khả dĩ của hệ thống. Tập này có thể hữu hạn hoặc đếm được vô hạn, song trong thực tế thường làm việc với tập hữu hạn để tính toán thuận tiện.

Ma trận xác suất chuyển tiếp $P=[p_{ij}]$ với:

$p_{ij}=P\bigl(X_{n+1}=s_j \mid X_n=s_i\bigr),\quad \sum_j p_{ij}=1.$

Khi ma trận $P$ có cấu trúc đặc biệt (ví dụ chuỗi đối xứng, chuỗi lưới), ta có thể khai thác tính chất riêng để giảm thiểu chi phí tính toán.

• Phân phối ban đầu: vector $\pi^{(0)}=[\pi_i^{(0)}]$, $\sum_i\pi_i^{(0)}=1$.
• Bước chuyển: mỗi bước $n$ sử dụng $P$ để cập nhật phân phối.

Phân loại

Chuỗi Markov rời rạc (DTMC) thực hiện bước nhảy tại các chỉ số nguyên $n=0,1,2,\dots$. Thời gian giữa các bước không xem xét, chỉ tập trung vào thứ tự chuyển đổi giữa các trạng thái.

Chuỗi Markov liên tục (CTMC) thời gian chuyển trạng thái tuân theo phân phối mũ với tham số phụ thuộc vào trạng thái hiện tại. Công thức xác suất chuyển trong khoảng thời gian $t$ được cho bởi ma trận tốc độ $Q$:

$P(t)=\exp(Qt).$

Chuỗi Markov bậc cao cho phép phụ thuộc vào $k$ trạng thái trước đó, thay vì chỉ trạng thái hiện tại. Mặc dù gia tăng độ phức tạp, loại này phù hợp với các hệ thống có tính nhớ dài, ví dụ mô hình ngôn ngữ N-gram.

1. DTMC: rời rạc theo bước.
2. CTMC: liên tục theo thời gian.
3. Bậc $k$: phụ thuộc vào $k$ bước trước.

Tính chất cơ bản

Irreducibility: Một chuỗi Markov được gọi là không giảm (irreducible) nếu với mọi cặp trạng thái i và j, tồn tại số bước n sao cho xác suất chuyển từ i sang j sau n bước lớn hơn 0. Tính chất này đảm bảo toàn bộ không gian trạng thái liên thông như một khối duy nhất.

Recurrence và Transience: Trạng thái i được gọi là recurrent nếu chuỗi chắc chắn sẽ trở lại i nhiều lần (xác suất trở lại = 1), ngược lại là transient (xác suất trở lại < 1). Chuỗi không giảm có ít nhất một trạng thái recurrent.

Ergodicity: Chuỗi ergodic vừa không giảm vừa không kỳ quặc (aperiodic). Trong trường hợp này, phân phối trạng thái tiến tới một giới hạn duy nhất, độc lập với phân phối ban đầu.

Phân phối ổn định (Stationary Distribution)

Phân phối ổn định π* là nghiệm của hệ phương trình tuyến tính:

$\pi^* P = \pi^*,\quad \sum_i \pi_i^* = 1.$

Giải hệ này cho giá trị π* cho biết tỷ lệ thời gian dài hạn mà chuỗi dành ở mỗi trạng thái. Đối với chuỗi ergodic, khi số bước n→∞, phân phối phân tích Xn hội tụ về π* bất kể phân phối ban đầu.

• Công thức cân bằng: π_j^* = ∑_i π_i^* p_{ij}.
• Phương pháp giải: dùng phép thế trực tiếp hoặc giải thuật lặp lẻ (power method).
• Ứng dụng: ước lượng tần suất dài hạn, so sánh tính ổn định giữa các trạng thái.

Thuật toán ước lượng tham số

Ước lượng tần suất tương đối: Với dữ liệu quan sát đường chuyển trạng thái, ước lượng p̂_{ij} = n_{ij}/n_i, trong đó n_{ij} là số lần chuyển i→j, n_i tổng số lần ở i. Phương pháp đơn giản, không cần giả định phân phối.

Phương pháp Maximum Likelihood (MLE): Xác định ma trận chuyển P sao cho hàm likelihood L(P)=∏_i∏_j p_{ij}^{n_{ij}} đạt cực đại. Kết quả tương đương ước lượng tần suất tương đối khi quan sát đầy đủ.

Thuật toán Baum–Welch: Dùng cho Mô hình Chuỗi Markov ẩn (HMM). Là một dạng thuật toán Expectation-Maximization (EM) lặp để ước lượng đồng thời ma trận chuyển và phân phối quan sát. Chuỗi ẩn được suy diễn bằng thuật toán tiến-lùi (forward–backward).

1. Khởi tạo tham số (ngẫu nhiên hoặc heuristic).
2. Bước E: tính xác suất phụ trách (responsibilities) với forward–backward.
3. Bước M: cập nhật tham số để tối đa likelihood cục bộ.
4. Lặp đến khi tụ hội.

Ứng dụng tiêu biểu

Trong tài chính, Markov chain được dùng để mô hình hóa biến động tín dụng, dự đoán khả năng vỡ nợ của doanh nghiệp theo trạng thái xếp hạng tín nhiệm (SAS Insights).

Trong xử lý ngôn ngữ tự nhiên, Markov chain đơn giản (n-gram) xây dựng mô hình ngôn ngữ, dự đoán từ tiếp theo dựa trên k-1 từ trước đó (NLTK Documentation).

• Lý thuyết hàng chờ: mô phỏng hệ thống phục vụ, tối ưu hóa tài nguyên.
• Cảm biến sinh học: mô phỏng tín hiệu thần kinh, chuyển mạch ion.
• Mô phỏng hoạt động mạng: phân tích lưu lượng, tối ưu định tuyến.

Mở rộng và liên quan

Mô hình Markov ẩn (HMM): Thêm biến ẩn Zn mô tả trạng thái thực, quan sát Yn phụ thuộc Zn. HMM dùng trong nhận dạng giọng nói, sinh học phân tử (Murphy HMM Tutorial).

Quasi-birth–Death Processes: Mở rộng cho các hệ hàng chờ nhiều cấp, trạng thái được phân thành cấp con (levels), dùng ma trận block để mô tả chuyển đổi (SIAM Journal).

Chuỗi Markov đa chiều: Trạng thái là vector (Xn(1),…,Xn(d)), dùng trong mô phỏng hệ phức hợp, ví dụ hệ thống sản xuất, mạng giao thông.

Tài liệu tham khảo

• Britannica: Markov Chain
• SAS Insights: Markov Models
• NLTK Documentation: N-gram Models
• Murphy: HMM Tutorial
• Grimmett, G. & Stirzaker, D. (2001). Probability and Random Processes. Oxford University Press.